/*
	创建时间:15点39分 2020年9月6日 
	GIT：https://gitee.com/wangchsoft/Cexcercise/blob/master/17%E9%AB%98%E7%BA%A7%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A1%A8%E7%A4%BA/%E5%9B%BE/%E5%9B%BE%E7%9A%84%E7%BB%83%E4%B9%A0.c
	compiler：MSVC based on c11
	notice:这个程序包含以下内容:
	                       -图的建立
						     -邻接矩阵
							 -邻接表
						   -ADT
						     -队列
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int vertex;//vertex意为顶点
typedef int edge;//edge表示边
/*该程序所需要的基本数据类型的封装函数*/
/*队列ADT
	这里使用的队列是非环形，每一次出队就把数据全都挪到队尾
*/
int* createQue(int n); //创建队列（输入值为预判的最大队列元素），返回值为NULL或一个具体值。
int enQue(int* q, int n,int num);  //将一个数排列到指定队列之中，如果成功返回1，否则返回0,num输入队列的容纳量，n输入插入的数，q为指向队列的指针
int outQue(int* q,int num);  //将末尾的数推出队列并返回该元素的值，如果成功则返回值，否则返回-1
int isemptyQue(int* q); //判断该队列是否为空，若为空返回0，否则返回1；
void testQue(void); //测试这个队列是否构建成功；程序测试用！！！
void testprintQ(int* q,int num); //打印队列

/*建立该程序的图-邻接矩阵方式实现( adjacent matrix)*/
int **createAM(vertex n);//创建一个邻接矩阵，并且把他们初始化
void testAM(int* a[],int n);//这是邻接矩阵的测试用例
void addAM(int* a[], vertex n, vertex m);//添加数据
/*建立该程序的图-邻接表方式实现adjacency list*/
struct AList
{
	int data;
	int known;//0代表未被读取，1代表已经被读取
	struct AList *child;
};
typedef struct AList ALhead;
ALhead* createAList(vertex n); //创建一个邻接表，返回数组表的表头
void testAL(ALhead* a, vertex n);//输入的n是顶点数
void addToList(vertex a, vertex b, vertex num, ALhead* putin);//创建每个顶点之间的边a->b
/*用户交互的子例程（该例程只用于创建一个图）*/
ALhead* communicate(vertex* n);//返回的是创建的表，n返回的是顶点的个数
int main(void)
{
	//testQue();
	/*int** test;
	test = createAM(12);
	testAM(test,12);*/
	ALhead* current,*new_list;
	vertex dingdian;
	current = communicate(&dingdian);
	return 0;
}

//创建队列（输入值为预判的最大队列元素），返回值为NULL或一个具体值，并且初始化这个队列的每一个元素为-1。
int* createQue(int n) 
{
	int* ret;
	ret = (int*)malloc(sizeof(int) * n);
	if (ret == NULL)	return ret;
	else
	{
		for (int cir = 0; cir < n; cir++)
			ret[cir] = -1;
	}
	return ret;
}
//将一个数排列到指定队列之中，如果成功返回1，否则返回0,队列的开头是zu[0],结尾是zu[n-1]，num输入队列的容纳量，n输入插入的数，q为指向队列的指针
int enQue(int* q, int n,int num) 
{
	int tmp = q[0],count=0;
	if (q[num - 1] != -1)	return 0;
	while (tmp != -1 && count < num)
	{
		count++;
		if(count<=num-1)	tmp = q[count];
	}
	q[count] = n;
	return 1;
}
 //将末尾的数推出队列并返回该元素的值，如果成功则返回值，否则返回-1,队列的开头是zu[0],结尾是zu[n-1]
int outQue(int* q,int num) 
{
	int ret = q[0];
	for (int cir = 0; cir < num; cir++)
		q[cir - 1] = q[cir];
	q[num - 1] = -1;
	return ret;
}
//判断该队列是否为空，若为空返回0，否则返回1；
int isemptyQue(int* q) 
{
	if (q[0] == -1)	return 0;
	else return 1;
}
//测试这个队列是否构建成功；程序测试用！！！
void testQue(void) 
{
	int *qu,tmp=-100;
	qu = createQue(8);
	if (qu != NULL)
	{
		enQue(qu, 2, 8);
		testprintQ(qu, 8);
		enQue(qu, 3, 8);
		testprintQ(qu, 8);
		enQue(qu, 125, 8);
		testprintQ(qu, 8);
		tmp = outQue(qu, 8);
		printf("%d\n", tmp);
		testprintQ(qu, 8);
		tmp = outQue(qu, 8);
		printf("%d\n", tmp);
		testprintQ(qu, 8);
		tmp = outQue(qu, 8);
		printf("%d\n", tmp);
		testprintQ(qu, 8);
	}
	else printf("error\n");
}
//打印队列
void testprintQ(int* q, int num) 
{
	for (int cir = 0; cir < num; cir++)
		printf("%4d", q[cir]);
	printf("\n");
}
//创建一个邻接矩阵，并且把他们初始化
int** createAM(vertex n)
{
	int** ret;
	ret = (int**)malloc(sizeof(int*) * n);
	for (int cir = 0; cir < n; cir++)
	{
		ret[cir] = (int*)malloc(sizeof(int) * n);
	}
	for (int cir = 0; cir < n; cir++)
	{
		for (int cir2 = 0; cir2 < n; cir2++)
		{
			if (cir != cir2)	ret[cir][cir2] = 0;
			else ret[cir][cir2] = -1;
		}
	}
	return ret;
}
//这是邻接矩阵的测试用例
void testAM(int* a[],int n)
{
	for (int cir=0; cir < n; cir++)
	{
		for (int cir2 = 0; cir2 < n; cir2++)
			printf("%2d", a[cir][cir2]);
		printf("\n");
	}
}
void addAM(int* a[], vertex n, vertex m)//添加数据
{
	a[n][m] = 1;
	a[m][n] = 1;
}
/*邻接表的子例程*/
ALhead* createAList(vertex n)//创建一个邻接表，返回数组表的表头，并且初始化所有的点
{
	ALhead* ret;
	ret = (ALhead*)malloc(sizeof(ALhead) * n);
	if (ret == NULL)	return ret;
	else
	{
		for (int cir = 0; cir < n; cir++)
		{
			ret[cir].data = cir + 1;
			ret[cir].child = NULL;
			ret[cir].known = 0;
		}
	}
	return ret;
}
void addToList(vertex a, vertex b,vertex num,ALhead*putin)//创建每个顶点之间的边a->b
{
	for (int cir = 0; cir < num; cir++)
	{
		if (putin[cir].data == a)
		{
			ALhead* addin;
			addin = (ALhead*)malloc(sizeof(ALhead));
			if (addin != NULL)
			{
				addin->child = NULL;
				addin->data = b;
				addin->known = 0;
				ALhead* tmp = putin + cir;
				while (tmp->child != NULL)	tmp = tmp->child;
				tmp->child = addin;
			}
			break;
		}
	}
}
void testAL(ALhead* a, vertex n)//输入的n是顶点数
{
	printf("*你所创建的邻接表如下->\n");
	for (int cir = 0; cir < n; cir++)
	{
		printf("%d->", a[cir].data);
		ALhead* tmp = a + cir;
		while (tmp->child != NULL)
		{
			tmp = tmp->child;
			printf("%d->", tmp->data);
		}
		printf("\n");
	}
}

/*用户交互的子例程（该例程只用于创建一个图）*/
ALhead* communicate(vertex *n)
{
	printf("***************************图的练习(测试用例)***************************\n\n");
	printf("*	NOTICE:该程序只提供测试样例，用户需要合法输入，不带输入检查!!\n");
	printf("*	TIME:14点36分 2020年9月7日,编写\n");
	printf("*	Basd on C11，msvc\n\n");
	int ch;
	ALhead* retu;
	vertex chuan;//这个表示顶点的总数
	printf("***************************初始化图(测试用例)***************************\n\n");
	printf("*该程序默认使用邻接表来实现,也提供了邻接矩阵的样例,需要的自行修改\n");
	printf("*	输入初始化表的大小(各个表头的默认初始值为1->n,n为输入值):");
	scanf_s("%d", &chuan);
	retu=createAList(chuan);
	if (retu != NULL)
	{
		printf("*Success!\n");
		testAL(retu, chuan);
	}
	printf("*选择是否连接顶点,输入0并回车以退出,输入除0外单个字母以继续:");
	scanf_s("%d", &ch);
	while (ch != 0)
	{
		printf("*你将输入两个值x,y:这两个值的方向设定为 x->y\n");
		vertex n, m;
		printf("*输入x值:");
		scanf_s("%d", &n);
		printf("*输入y值:");
		scanf_s("%d", &m);
		addToList(n, m, chuan, retu);//创建每个顶点之间的边a->b
		printf("*选择是否连接顶点,输入0并回车以退出,输入除0外单个字母以继续:");
		scanf_s("%d", &ch);
	}
	testAL(retu, chuan);
	return retu;
}
/*topological sorting*/
